package org.niu.str;

public class MinWindow {
    public String minWindow(String s,String t){

        int[] mp = new int[128];

        int l = 0, r = 0;
        int size = Integer.MAX_VALUE;
        int start = 0;
        int needCount = t.length();
        for (int i = 0; i < t.length(); i++) {
            mp[t.charAt(i)]++;
        }
        while(r < s.length()){
            char c = s.charAt(r);
            if (mp[c] > 0){
                needCount--;
            }
            // 无论是谁都mp[c]--
            mp[c]--;
            if(needCount == 0){
                while (l < r && mp[s.charAt(l)] < 0){
                    mp[s.charAt(l)]++;
                    l++;
                }
                if(r-l+1<size){
                    size = r-l+1;
                    start = l;
                }
                // 重新维护，寻找下一个边界
                mp[s.charAt(l)]++;
                l++;
                needCount++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE ? "":s.substring(start,start+size);
    }
}
